#define _CRT_SECURE_NO_WARNINGS 1
//int numDecodings(char* s) {
//    int len = strlen(s);
//    if (len == 2 && *s == '0')
//        return 0;
//    if (len == 2 && ((s[0] - '0') * 10 + (s[1] - '0')) > 26)
//        return 0;
//    if (s[len - 1] == '0' && ((s[len - 2] - '0') * 10 + (s[len - 1] - '0')) > 26)
//        return 0;
//    int* dp = (int*)malloc(sizeof(int) * len);
//    dp[0] = 1;
//    if (s[1] == '0')
//        dp[1] = 1;
//    else
//        dp[1] = 2;
//    for (int i = 2; i < len; i++) {
//        int left1 = 0;
//        int left2 = 0;
//        if (dp[i] == '0')
//            left1 = 0;
//        else
//            left1 = dp[i - 1];
//        if (((dp[i - 1] - '0') * 10 + (dp[i] - '0')) > 26)
//            left2 = 0;
//        else
//            left2 = dp[i - 2];
//        dp[i] = left1 + left2;
//    }
//    return dp[len - 1];
//
//}

//int numDecodings(char* s) {
//    int len = strlen(s);
//    int* dp = (int*)calloc(len, sizeof(int));
//    dp[0] = s[0] != '0';
//    if (len == 1)
//        return dp[0];
//    int tmp = (s[0] - '0') * 10 + s[1] - '0';
//    if (s[0] != '0' && s[1] != '0')
//        dp[1] += 1;
//    if (tmp >= 10 && tmp <= 26)
//        dp[1] += 1;
//    for (int i = 2; i < len; i++) {
//        if (s[i] != '0')
//            dp[i] += dp[i - 1];
//        int tmp = (s[i - 1] - '0') * 10 + s[i] - '0';
//        if (tmp >= 10 && tmp <= 26)
//            dp[i] += dp[i - 2];
//
//    }
//    return dp[len - 1];
//
//}